package leetcode_day._2021._202105._2131;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/22 19:57
 * 黑板异或游戏
 * 算法：数学
 * 从两个角度判断，先手必胜态和后手必败态
 * 先手必胜：如果所有数字异或和为 0，那么肯定胜利
 * 后手必败态：假设先手操作后剩余数字的异或和为 sum(sum != 0)，
 * 因为是后手必败态，所以后手随便去掉一个数就会使结果为 0，则满足
 * sum ^ num[0] = ... = sum ^ num[k] = 0
 * ==> sum ^ num[0] ... ^ sum ^ num[k] = 0(下面式子可以退出有几个 sum, 有几个 sum 就剩余几个数字)
 * ==> (sum ^ ... ^ sum) ^ (num[0] ^ ... ^ num[k]) = 0
 * ==> (sum ^ ... ^ sum) ^ sum = 0
 * 要满足上式，则要求 sum 的个数为偶数个
 * 可以推出先手操作后剩余奇数个数字, 所以操作前的数字个数为偶数个
 * 所以后手失败态要求数字个数为偶数个
 */
public class _22_810 {

    public boolean xorGame(int[] nums) {
        int sum = 0;
        for (int num : nums) sum ^= num;
        return sum == 0 || nums.length % 2 == 0;
    }

}
